968. 监控二叉树

Similar Question

Solution Tips

方案一: 贪心

叶子节点的状态没处理好, 由子节点的状态, 决定父节点的状态, 并且状态有 3 种, 感觉也有其他类似的题目

返回 true or false 的类型还是常见的, 这题进阶了一下

var minCameraCover = function(root) {
    let result = 0
    function traversal(cur) {
        if(cur === null) {
            return 2
        }

        let left = traversal(cur.left)
        let right = traversal(cur.right)

        if(left === 2 && right === 2) {
            return 0
        }

        if(left === 0 || right === 0) {
            result++
            return 1
        }

        if(left === 1 || right === 1) {
            return 2
        }

        return -1
    }

    if(traversal(root) === 0) {
        result++
    }

    return result

};

错误的 case

var minCameraCover = function(root) {
    // 只要有2个子节点, 就一定要自己监视? 从低往上
    // 只要有有2个子节点, 而且不是两个都有x, 就需要自己监视
    // 所以是一个子树问题, 分支思想
    if (root === null) return 0;
    if (root.left === root.right) return 1;
    let res = 0;
    dfs(root);
    return res;

    function dfs(node) {
        // 叶子节点不需要装摄像头, 所以返回 true
        // 返回自己是否被监视了, 装了摄像头为 2
        if (node === null) return 1;

        const left = dfs(node.left);
        const right = dfs(node.right);
        // 有一个儿子没有被监视自己就需要装
        // 两个儿子都被监视了, 自己就不需要装
        // 自己没装摄像头, 但是被儿子的摄像头覆盖了为 0
        const check = left + right

        // 1 + 1 自己不需要, 两个儿子已经监控好自己了
        // 0 + 1 自己不需要, 但要去监控另一个儿子
        // 0 + 0 自己需要, 可监控两个儿子
        if (check < 2) {
            res++;
            return 1;
        }
        else {
            return 0;
        }

    }
};
console.log(minCameraCover(t.root))